# 数组中的最长山脉： https://leetcode-cn.com/problems/longest-mountain-in-array/submissions/

class Solution:
    def longestMountain(self, arr: list) -> int:
        """
            可以使用两个指针进行判断，是否为山脉数组，并指向山脉数组的左右边界，确定山脉数组长度.
            初始化 left， right. right = left + 1
        """
        left = 0
        right = left + 1
        n = len(arr)
        maxLen = 0
        # 能构成山脉最少有三个元素， 这里 left + 2 < n
        while left + 2 < n:
            # 1. left < right 才有可能构成山脉
            if arr[left] < arr[right]:
                # 3. 找山顶
                while right + 1 < n and arr[right] < arr[right + 1]:
                    right += 1
                # 如果右边的 等于当前位置, 或者是递增的没有右边界了，根据定义，也构不成山脉
                if right + 1 >= n or arr[right] == arr[right + 1]:
                    left, right = right, right + 1    
                    continue
                # 4. 找山脉右边界
                while right + 1 < n and arr[right] > arr[right + 1]:
                    right += 1
                # 5. 计算山脉长度
                maxLen = max(maxLen, right - left + 1)
                # 6.更新 left，right
                left, right = right, right + 1    
            # 2. 否则肯定构不成山脉
            else:
                left, right = right, right + 1

        return maxLen
        

# 优化上面的代码
class Solution:
    def longestMountain(self, arr: list) -> int:
        """
            可以使用两个指针进行判断，是否为山脉数组，并指向山脉数组的左右边界，确定山脉数组长度.
            初始化 left， right. right = left + 1
        """
        left = 0
        right = left + 1
        maxLen, n = 0, len(arr)
        # 能构成山脉最少有三个元素， 这里 left + 2 < n
        while left + 2 < n:
            # 1. left < right 才有可能构成山脉
            if arr[left] < arr[right]:
                # 3. 找山顶
                while right + 1 < n and arr[right] < arr[right + 1]:
                    right += 1
                # 4. 找山脉右边界
                while right + 1 < n and arr[right] > arr[right + 1]:
                    right += 1
                # 5. 计算山脉长度,  要判断当前是否能构成山脉数组
                if arr[right - 1] > arr[right]:
                    maxLen = max(maxLen, right - left + 1)
                   
            # 2. 构不成山脉, 更新 left ，right
            left, right = right, right + 1 

        return maxLen